'''
难度 中等
题目链接 https://leetcode.cn/problems/maximum-area-of-a-piece-of-cake-after-horizontal-and-vertical-cuts/description/
'''

from typing import List

class Solution:
    def maxArea(self, h: int, w: int, horizontalCuts: List[int], verticalCuts: List[int]) -> int:
        def 获取最大间隔(maxNum: int, cuts: List[int]) -> int:
            # 添加外围边界
            cuts.insert(0, 0)
            cuts.append(maxNum)
            # 避免防止未排序结果错误
            cuts.sort()
            最大间隔 = 0
            for i in range(1, len(cuts)):
                最大间隔 = max(最大间隔, cuts[i] - cuts[i - 1])

            return 最大间隔
        
        模 = 10**9 + 7

        return 获取最大间隔(h, horizontalCuts) * 获取最大间隔(w, verticalCuts) % 模
    

if __name__ == '__main__':
    s = Solution()
    参数 = [
        [5, 4, [1,2,4], [1,3]],
        [5, 4, [3,1], [1]],
        [5, 4, [3], [3]],
    ]
    预期 = [
        4,
        6,
        9,
    ]
    for k,v in enumerate(参数):
        r = s.maxArea(v[0], v[1], v[2], v[3])
        if r != 预期[k]:
            print("第{}个case不通过 期望={} 结果={}\n".format(
                k+1,
                预期[k],
                r
            ))